package one.three.thirtySeven;

import java.util.Arrays;

public class Josephus {

	public static int[] josephusBack(int s, int a) {
		int[] r = new int[s];
		int idx = 0;
		Queue<Integer> q = new Queue<Integer>();
		for (int i = 0; i < s; i++) {
			q.enqueue(i);
		}
		System.out.println(q);

		while (idx < s - 1) {
			boolean hit = false;
			int last = -1;
			int c = 0;
			int[] tmp = new int[s];
			int tmpIdx = 0;
			while (!q.isEmpty()) {
				c++;
				System.out.println("[c:" + c);
				int d = q.dequeue();
				if (c % a == 0) {

					System.out.println("*" + d + "]");
					r[idx] = d;
					last = tmpIdx;
					idx++;
					hit = true;
				} else {
					tmp[tmpIdx] = d;
					if (hit) {
						last = tmpIdx;
						hit = false;
					}
					tmpIdx++;
				}
			}
			System.out.println("tmpIdx:" + tmpIdx);
			System.out.println("idx:" + idx);
			System.out.println("last:" + last);
			System.out.println(Arrays.toString(tmp));
			q = new Queue<Integer>();
			if (last >= 0) {
				for (int i = last; i < tmpIdx; i++) {
					q.enqueue(tmp[i]);
				}
				for (int i = 0; i < last; i++) {
					q.enqueue(tmp[i]);
				}
			} else {
				for (int i = 0; i < tmpIdx; i++) {
					q.enqueue(tmp[i]);
				}
			}

			System.out.println(q);
			System.out.println("\n\n" + idx + "\n\n");
		}
		r[s - 1] = q.dequeue();
		System.out.println(Arrays.toString(r));
		return r;
	}

	public static int[] josephus(int s, int a) {
		int[] r = new int[s];
		int idx = 0;
		Queue<Integer> q = new Queue<Integer>();
		//for (int i = 0; i < s; i++) {
		//	q.enqueue(i);
		//}
		for (int i = 0; i < s; i++) {
			q.enqueue(i+1);
		}
		System.out.println(q);

		while (q.size() > 0) {
			if (q.size() >= a) {
				Queue<Integer> tmp = new Queue<Integer>();
				int max = q.size() / a;
				int hit = 0;
				int c = 0;
				while (!q.isEmpty()) {
					int d = q.dequeue();
					c++;
					System.out.println("c:" + c + ",d:" + d);
					if (c % a == 0) {
						r[idx] = d;
						idx++;
						hit++;
						System.out.println("r:" + Arrays.toString(r));
					} else {
						if (hit == max) {
							tmp.pushTail(d);
						} else {
							tmp.enqueue(d);
						}
					}
				}
				q = tmp;
				System.out.println("tmp:" + tmp);
			} else {
				a = a % q.size();
				if (a == 0) {
					r[idx] = q.dequeue();
					idx++;
				} else {
					Queue<Integer> tmp = new Queue<Integer>();
					int max = q.size() / a;
					int hit = 0;
					int c = 0;
					while (!q.isEmpty()) {
						int d = q.dequeue();
						c++;
						System.out.println("c:" + c + ",d:" + d);
						if (c % a == 0) {
							r[idx] = d;
							idx++;
							hit++;
							System.out.println("r:" + Arrays.toString(r));
						} else {
							if (hit == max) {
								tmp.pushTail(d);
							} else {
								tmp.enqueue(d);
							}
						}
					}
					q = tmp;
				}
				//System.out.println("tmp:" + tmp);
			}
		}
		System.out.println("end:" + q.size());
		System.out.println("r:"+Arrays.toString(r));
		return null;
	}

	public static void main(String[] args) {
		josephus(6, 3);
		// System.out.println(8 / 3);
	}

}
